581. 最短无序连续子数组

Similar Question

Solution Tips

方案一: 排序 + Diff 对比

排序后比对最左和最右的变化，中间即是

var findUnsortedSubarray = function(nums) {
  const sorted = [...nums].sort((a,b)=>a-b)
  let left = null
  for (let i = 0; i < nums.length; i++) {
    if(nums[i]!==sorted[i]){
      left = i
      break
    }
  }
  let right = null
  for (let i = nums.length-1;  i > 0; i--) {
    if(nums[i]!==sorted[i]){
      right = i
      break
    }
  }
  // 如果是已排序的，left和right都是null
  // 如果是顶点不同，left和right等于length
  return left===null?0:right - left + 1
}

方案二: 双指针

从左往右找到第一个不在正确位置的大值

var findUnsortedSubarray = function(nums) {
  const len = nums.length
  //结束值赋为-2是考虑在数组本身就是有序时,return也可以给出正确值
  let start =-1,
      end = -2
      max = nums[0],
      min = nums[len-1]
  for (let i = 0,j=len-1; i < nums.length && j>=0; i++,j--) {
    if(max>nums[i]) end = i
    else max = nums[i]

    if(min<nums[j]) start = j
    else min = nums[j]
  }
  return end - start + 1
}